package tree;

/**
 * @Classname BinarySearchTree
 * @Author happytaohaha
 * @Date 2020/3/7
 * @Description 二叉搜索树
 */
public class BinarySearchTree<T extends Comparable<T>> {

    /**
     * 内部节点
     *
     * @param <T>
     */
    private static class Node<T> {
        private T data;
        private Node<T> left;
        private Node<T> right;

        public Node(T data) {
            this(data, null, null);
        }

        public Node(T data, Node<T> left, Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 私有变量 根节点root
     */
    private Node<T> root;

    /**
     * 置空
     */
    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T value) {
        return contains(value, root);
    }

    private boolean contains(T value, Node<T> root) {
        if (root == null) {
            return false;
        }
        int result = root.data.compareTo(value);
        if (result < 0) {
            return contains(value, root.right);
        } else if (result > 0) {
            return contains(value, root.left);
        } else {
            return true;
        }
    }

    public T findMin() {
        return findMin(root).data;
    }

    private Node<T> findMin(Node<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public T findMax() {

        return findMax(root).data;
    }

    private Node<T> findMax(Node<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public void insert(T value) {

        root = insert(value, root);
    }

    /**
     * 插入元素，找到应该插入的位置往下搜索
     *
     * @param value
     * @param root
     * @return
     */
    private Node<T> insert(T value, Node<T> root) {
        if (root == null) {
            return new Node<T>(value, null, null);
        }
        int result = value.compareTo(root.data);
        if (result < 0) {
            root.left = insert(value, root.left);
        } else if (result > 0) {
            root.right = insert(value, root.right);
        }
        return root;
    }

    public void remove(T value) {
        root = remove(value, root);
    }

    /**
     * 　remove方法:在查找树的代码实现中,最难得是删除,因为这涉及到三种情况:
     * 这两种情况合并
     * 　　*　 被删除节点是树叶节点(没有子树):最简单,直接删除,将该节点置为null即可
     * 　　*　 被删除节点有一个子节点(左子树或右子树):是该节点的父节点指向该节点的子节点(左或右).见图1
     *
     * root.left != null && root.right != null
     * 　　*　 被删除节点有两个子节点:用其右子树中的最小值代替该节点上的值,删除其右子树上的最小值.见图2.
     *
     * @param value
     * @param root
     * @return
     */
    private Node<T> remove(T value, Node<T> root) {
        if (root == null) {
            return null;
        }
        int result = value.compareTo(root.data);
        if (result < 0) {
            root.left = remove(value, root.left);
        } else if (result > 0) {
            root.right = remove(value, root.right);

        } else if (root.left != null && root.right != null) {
            root.data = findMin(root.right).data;
            root.right = remove(root.data, root.right);
        } else {
            root = (root.left != null) ? root.left : root.right;
        }
        return root;
    }


    //中序遍历打印
    public void printTree() {
        printTree(root);
    }

    private void printTree(Node<T> t) {

        if (t != null) {
            printTree(t.left);
            System.out.println(t.data);
            printTree(t.right);
        }
    }


    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        bst.insert(5);
        bst.insert(7);
        bst.insert(3);
        bst.insert(1);
        bst.insert(9);
        bst.insert(6);
        bst.insert(4);
        System.out.println("最小值:" + bst.findMin());
        System.out.println("最大值:" + bst.findMax());
        System.out.println("查找元素9是否存在:" + bst.contains(9));
        System.out.println("查找元素8是否存在:" + bst.contains(8));
        bst.remove(9);
        System.out.println("遍历二叉树");
        bst.printTree();

    }

}
